//
// Created by francklinson on 2021/7/6.
//

#include <vector>
#include <iostream>
#include <queue>
#include <climits>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
     * 层序遍历
     * @param root
     * @return
     */
    vector<int> largestValues(TreeNode *root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            int maxVal = INT_MIN;
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                // 更新最大值
                maxVal = max(maxVal, p->val);
                if (p->left != nullptr) q.push(p->left);
                if (p->right != nullptr) q.push(p->right);
            }
            ans.push_back(maxVal);
        }
        return ans;
    }
};

int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(3), n3 = TreeNode(2), n4 = TreeNode(5), n5 = TreeNode(3), n6 = TreeNode(9);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;
    Solution sol;
    auto ans = sol.largestValues(&n1);
    for (auto &x:ans) cout << x << endl;
    return 0;
}